from random import choice
from typing import Union

failures_list = ["В этом лабиринте одни тупики!", "Выход так близко, но недостижим!", "Мы потеряны в лабиринте разума.", "Впав в заблуждений лабиринт, отметьте вход. Коли прозреете, то он же будет выход.",
"Введёшь кого-то в заблуждение — а там лабиринт без выхода!", "Не заводите других в лабиринты, из которых не умеете выбраться сами.","Сплин: 'Выхода нет!'", "Гендальф: 'Ты не пройдешь!'"]


def can_exit(lst: list) -> Union[bool, str]:
    """Функция возвращает истину, если можно пройти двигаясь по нулям влево-вправо-вверх-вниз
    с левого верхнего угла матрицы до правого нижнего.
    :param lst: матричный двумерный список
    :return: True если возможно, иначе - выводит сообщение из списка, выбранное случайным образом.
    """
    marker: int = 3 # Маркер для прохода матрицы
    if lst[0][0] == 0:
        lst[0][0] = marker
    for i in range(len(lst)):
        for j in range(len(lst[i])):
            if lst[i][j] == marker:
                # Обработка граничащих с маркером позиций
                for x in range(-1, 2):
                    for y in range(-1, 2):
                        # Проверка движение вверх-вниз-влево-вправо
                        if x != y and x + y != 0:
                            # Проверка невыхода за границы матрицы
                            if i + x >= 0 and j + y >= 0 and i + x < len(lst) and j + y < len(lst[i]):
                                # Меняем 0 на маркер
                                if lst[i + x][j + y] == 0:
                                    lst[i + x][j + y] = marker
    if lst[-1][-1] == marker:
        return True, lst
    return choice(failures_list), lst

if __name__ == "__main__":
    assert can_exit([
        [0, 1, 1, 1, 1, 1, 1],
        [0, 0, 1, 1, 0, 1, 1],
        [1, 0, 0, 0, 0, 1, 1],
        [0, 1, 1, 1, 0, 0, 1],
        [0, 1, 1, 1, 1, 0, 0]
    ]) == True

    assert can_exit([
        [0, 1, 1, 1, 1, 1, 1],
        [0, 0, 1, 0, 0, 1, 1],
        [1, 0, 0, 0, 0, 1, 1],
        [1, 1, 0, 1, 0, 0, 1],
        [1, 1, 0, 0, 1, 1, 1]
    ]) != True

    assert can_exit([
        [0, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 1, 0, 0],
        [1, 1, 1, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1, 0],
        [1, 1, 1, 1, 1, 1, 1]
    ]) != True

    assert can_exit([
        [0, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 1, 0, 0],
        [1, 1, 1, 0, 0, 0, 0],
        [1, 0, 0, 0, 1, 1, 0],
        [1, 1, 1, 1, 1, 1, 0]
    ]) == True

    assert can_exit([
        [0, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 1, 0, 0],
        [1, 1, 1, 0, 1, 0, 0],
        [1, 0, 0, 1, 1, 1, 0],
        [1, 1, 1, 1, 1, 1, 0]
    ]) != True

    assert can_exit([
        [0, 1, 1, 1, 1, 1, 1],
        [1, 0, 1, 1, 1, 1, 1],
        [1, 1, 0, 1, 1, 1, 1],
        [1, 1, 1, 0, 1, 1, 1],
        [1, 1, 1, 1, 0, 0, 0]
    ]) != True


print(can_exit([
    [0, 1, 1, 1, 1, 1, 1],
    [0, 0, 1, 1, 0, 1, 1],
    [1, 0, 0, 0, 0, 1, 1],
    [0, 1, 1, 1, 0, 0, 1],
    [0, 1, 1, 1, 1, 0, 0]
    ]))

print(can_exit([
    [0, 1, 1, 1, 1, 1, 1],
    [0, 0, 1, 0, 0, 1, 1],
    [1, 0, 0, 0, 0, 1, 1],
    [1, 1, 0, 1, 0, 0, 1],
    [1, 1, 0, 0, 1, 1, 1]
    ]))

print(can_exit([
    [0, 1, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
    [1, 1, 1, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 0],
    [1, 1, 1, 1, 1, 1, 1]
    ]))

print(can_exit([
    [0, 1, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
    [1, 1, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 1, 1, 0],
    [1, 1, 1, 1, 1, 1, 0]
    ]))

print(can_exit([
    [0, 1, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
    [1, 1, 1, 0, 1, 0, 0],
    [1, 0, 0, 1, 1, 1, 0],
    [1, 1, 1, 1, 1, 1, 0]
    ]))

print(can_exit([
    [0, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 1],
    [1, 1, 0, 1, 1, 1, 1],
    [1, 1, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 0, 0, 0]
    ]))

print(can_exit([
    [0, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 0, 1, 1, 1, 0, 1, 1],
    [1, 1, 1, 0, 1, 0, 1, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 0]
    ]))

print(can_exit([
    [0, 0, 1, 0, 0, 0, 0, 0, 0],
    [1, 0, 1, 0, 1, 1, 1, 1, 0],
    [1, 0, 0, 0, 1, 1, 0, 1, 0],
    [1, 1, 1, 1, 1, 0, 1, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1, 0]
    ]))
